package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_784_字母大小写全排列 {
    //测试
    public static void main(String[] args) {
        System.out.println((int)'z');//97
        System.out.println((int)'Z');//65
        System.out.println(new 力扣_784_字母大小写全排列().letterCasePermutation("a1b2").toString());
    }

    /**
    题目：给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
     返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

     示例 1：
     输入：s = "a1b2"
     输出：["a1b2", "a1B2", "A1b2", "A1B2"]

     示例 2:
     输入: s = "3z4"
     输出: ["3z4","3Z4"]


    分析：【P ❤💜💞】
       1.回溯法【组合：不需要位图记录是否已使用元素】.
             :其实就是字母的位置需不需要变化，【组合每个位置的是否变化情况】
             --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

       再次总结：回朔关键点 通过分析发现，回朔法实现的三大技术关键点分别是：
         1.一条路走到黑
         2.回退一步
         3.另寻他路

    边界值 & 注意点：
       1.
     **/
    public List<String> letterCasePermutation(String s) {
        List<String> res = new ArrayList<>();
        res.add(s);
        char[] chars = s.toCharArray();
        recursion(chars,0,res);
        return res;
    }

    private void recursion(char[] chars, int start, List<String> res) {
        for (int i = start; i < chars.length; i++) {
            if(chars[i]>96 && chars[i]<123){
                chars[i]-=32;
                res.add(String.valueOf(chars));
                recursion(chars,i+1,res);
                chars[i]+=32;
            }else if( chars[i]>64 && chars[i]<91){
                chars[i]+=32;
                res.add(String.valueOf(chars));
                recursion(chars,i+1,res);
                chars[i]-=32;
            }
        }
    }
}
